RAM circuits are wed-known data storage devices that store data values in an array of addressed memory locations. To determine whether a particular data value is stored in a typical RAM, an address-based data searching method is performed. Data values are sequentially read out from the RAM and compared with the particular data value. Specifically, a series of addresses are transmitted to an address port of the RAM, thereby causing data values to be read out from the memory locations associated with the addresses and transmitted to an output port of the RAM. A separate comparator circuit is then used to compare each of the output data values with the searched-for data value, and to generate a signal when a match occurs. When a large number of data values are searched, such address-based search operations are very time consuming because only one data value is searched/compared each dock cycle.
Content-addressable-memory (CAM) circuits are a particular type of data storage device in which a data value is searched for by its content, rather than by its address. Data values are stored (pre-loaded) in CAM circuits such that each data value is assigned to a row or column of an array of CAM cells. To determine whether a particular data value is stored in the CAM circuit, a content-based data match operation is performed in which the searched-for data value is simultaneously compared with the rows/columns containing the pre-loaded data values. When one or more of the pre-loaded data values match the searched-for data value, a “match” signal is generated by the CAM circuit, along with an address indicating the storage location of the stored data value. By simultaneously comparing the searched-for data value with several pre-loaded data values, a CAM circuit is able to simultaneously check multiple stored data values in a single clock cycle. In comparison to RAM, CAM circuits significantly reduce the search time needed to locate a particular data value from a large number of data values. One type of CAM, referred to as ternary-content-addressable-memory (TCAM), stores ternary bit values, having three possible states, for example, logic one, logic zero, and wildcard (*). A stored bit having the wildcard * value will match a bit of a search word having either a logic one or a logic zero value. For example, an input search word 1010 will match multiple ternary values including: 1010, *010, 1*10, 10*0, 101*, **10, 1**0, 10**, ***0, 1***, and ****. Ternary values stored in a TCAM may be referred to as rules. The searched-for data value may be referred to as a search key.
Existing TCAM circuits are comparatively expensive and power-hungry, and do not scale well with respect to clock rate or circuit area as the number of bits in the stored rules is increased. While various algorithmic TCAMs have been proposed, the memory requirements of these algorithmic TCAMs often depend on the distribution of wildcard bits in the ternary rules to be stored and searched by the TCAM. For example, an algorithmic TCAM configured to store and search N W-bit rules concurrently may require as many as O(NW) memory cells.